package m202405.d13;

import com.sun.source.tree.Tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/13 16:43
 */
public class Q236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, Boolean> pMap = new HashMap<>();
        Map<TreeNode, Boolean> qMap = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode commonRoot = root;
        queue.offer(root);
        while (!queue.isEmpty()) {
            Queue<TreeNode> tempQueue = new LinkedList<>();
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (isChildren(node, p, pMap) && isChildren(node, q, qMap)) {
                    commonRoot = node;
                }
                if (node.left != null) {
                    tempQueue.offer(node.left);
                }
                if (node.right != null) {
                    tempQueue.offer(node.right);
                }
            }
            queue = tempQueue;
        }
        return commonRoot;
    }

    private boolean isChildren(TreeNode node, TreeNode p, Map<TreeNode, Boolean> map) {
        if (node == null) {
            return false;
        }
        Boolean b = map.get(node);
        if (b != null) {
            return b;
        }
        boolean flag = isChildren1(node, p, map);
        map.put(node, flag);
        return flag;
    }

    private boolean isChildren1(TreeNode node, TreeNode p, Map<TreeNode, Boolean> map) {
        if (node == null) {
            return false;
        }
        if (node == p) {
            return true;
        }
        Boolean b = map.get(node);
        if (b != null) {
            return b;
        }
        return isChildren(node.left, p, map) || isChildren(node.right, p, map);
    }
}
